﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace QueuesAndStacks.DailyTemperatures
{
    class MainProject
    {
        static void Main(string[] args)
        {
            int[] nums = new int[] { 73, 74, 75, 71, 69, 72, 76, 73 };
            foreach (var item in DailyTemperatures(nums))
            {
                Console.WriteLine(item);
            }
            Console.ReadKey();
        }
        public static int[] DailyTemperatures(int[] temperatures)
        {
            //暴力解法
            //int[] dp = new int[temperatures.Length];
            //for (int i = 0; i < temperatures.Length; i++)
            //{
            //    int index = 0;
            //    for (int j = i; j < temperatures.Length; j++)
            //    {
            //        if (temperatures[i] < temperatures[j])
            //        {
            //            dp[i] = index;
            //            break;
            //        }
            //        else
            //            index++;
            //    }
            //}
            //return dp;

            //单调栈
            Stack<int> sta = new Stack<int>();
            int[] res = new int[temperatures.Length];
            sta.Push(0);
            for (int i = 1; i < temperatures.Length; i++)
            {
                while (sta.Count > 0)
                {
                    if (temperatures[i] > temperatures[sta.Peek()])
                    {
                        int index = sta.Pop();
                        res[index] = i - index;
                    }
                    else
                        break;
                }
                sta.Push(i);


                //if (sta.Count == 0)
                //{
                //    sta.Push(i);
                //}
                //else
                //{
                //    if (temperatures[i] > temperatures[sta.Peek()])
                //    {
                //        int index = sta.Pop();
                //        res[index] = i - index;
                //        sta.Push(i);
                //    }
                //    else
                //    {
                //        sta.Push(i);
                //    }
                //}

            }
            return res;
        }
    }
}
